package DataStructure.tree;


public class RedBlackTree<Key extends Comparable<Key>,Value> {
    private Node root;
    private int N;
    //红色链接
    private static final boolean RED=true;
    private static final boolean BLACK=false;

    //节点类
    private class Node{
        public Key key;
        public Value value;
        public Node left;
        public Node right;
        //由其父节点指向它链接的颜色
        public boolean color;

        public Node(Key key, Value value,Node left,Node right,boolean color){
            this.key=key;
            this.value=value;
            this.left=left;
            this.right=right;
            this.color=color;
        }
    }

    //获取树中元素个数
    public int size(){
        return N;
    }

    //判断当前节点指向父节点的链接是否为红色
    public boolean isRed(Node x){
        if (x==null){
            return false;
        }
        return x.color==RED;
    }

    //左旋转
    private Node rotateleft(Node h){
        //获取h节点的右子节点表示为x节点
        Node x = h.right;
        //让x节点的左子节点成为h节点的右子节点
        h.right=x.left;
        //让h成为x的左子节点
        x.left=h;
        //让x的color等于h的color
        x.color=h.color;
        //让h节点的color变为红色
        h.color=RED;
        return x;
    }

    //右旋
    private Node rotateRight(Node h){
        //获取h节点的左子节点表示为x节点
        Node x = h.left;
        //让x节点的右子节点成为h节点的左子节点
        h.left=x.right;
        //让h成为x的右子节点
        x.right=h;
        //让x的color等于h的color
        x.color=h.color;
        //让h节点的color变为红色
        h.color=RED;
        return x;
    }

    //颜色反转
    private void filpColors(Node h){
        //让当前节点变为红色
        h.color=RED;
        //左子节点和右子节点变为黑色
        h.left.color=BLACK;
        h.right.color=BLACK;
    }




    //在整个树上插入
    public void put(Key key,Value val){
        root = put(root,key,val);
        root.color=RED;//跟节点的颜色总是黑色
    }

    //在指定树h中完成插入并返回插入完成后新的树
    private Node put(Node h,Key key,Value val){
        //判断h是否为空，如果为空则直接返回一个红色节点
        if(h==null){
            N++;
            return new Node(key,val,null,null,RED);
        }
        //比较h节点的键和key的大小
        int cmp = key.compareTo(h.key);
        if(cmp<0){
            //继续往左
            h.left = put(h.left,key,val);
        }else if (cmp>0){
            //继续往右
            h.right = put(h.right,key,val);
        }else {
            //替换
            h.value=val;
        }
        //进行左旋：当当前节点h的左子节点为黑色，右子节点为红色，需要左旋
        if(isRed(h.right) && !isRed(h.left)){
            h=rotateleft(h);
        }
        //进行右旋:当当前节点h的左子节点和左子节点的左子节点都为红色,需要右旋
        if(isRed(h.left) && isRed(h.left.left)){
            h=rotateRight(h);
        }
        //颜色反转:当前结点的左子节点和右子节点都为红色时，要颜色反转
        if(isRed(h.left) && isRed(h.right)){
            filpColors(h);
        }
        return h;
    }


    //根据key从整个树中查找对应的值
    public Value get(Key key){
        return get(root,key);
    }

    //根据key从指定树中查找对应的值
    private Value get(Node x,Key key){
        if(x==null){
            return null;
        }

        //比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if(cmp<0){
            return get(x.left,key);
        }else if(cmp>0){
            return get(x.right,key);
        }else {
            return x.value;
        }
    }
}
